package top.lcm668.study.oj.demo;


/**
 * @author: Coder-Lcm
 * @date: 2021/10/2 20:33
 * 经典的斐波那契数列算法题
 */
public class Fiber {
    public static void main(String[] args) {
        System.out.println(solveV1(4));
        System.out.println(solveV2(5));
    }

    /**
     * 迭代法计算
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * @param n
     * @return
     */
    private static int solveV1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int a1 = 1, a2 = 1, a3 = 0;
        for (int i = 3; i <= n; i++) {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }

    /**
     * 递归实现
     * @param n
     * @return
     */
    private static int solveV2(int n) {
       if (n == 1 || n == 2) {
           return 1;
       }
       return solveV2(n - 2) + solveV2(n - 1);
    }
}
